package com.sheng.leetcode.year2023.month07.day11;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/07/11
 * <p>
 * 1911. 最大子序列交替和<p>
 * <p>
 * 一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。<p>
 * 比方说，数组 [4,2,5,3] 的交替和为 (4 + 5) - (2 + 3) = 4 。<p>
 * 给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 （子序列的下标 重新 从 0 开始编号）。<p>
 * 一个数组的 子序列 是从原数组中删除一些元素后（也可能一个也不删除）剩余元素不改变顺序组成的数组。<p>
 * 比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的一个子序列（加粗元素），但是 [2,4,2] 不是。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [4,2,5,3]<p>
 * 输出：7<p>
 * 解释：最优子序列为 [4,2,5] ，交替和为 (4 + 5) - 2 = 7 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [5,6,7,8]<p>
 * 输出：8<p>
 * 解释：最优子序列为 [8] ，交替和为 8 。<p>
 * <p>
 * 示例 3：<p>
 * 输入：nums = [6,2,1,2,4,5]<p>
 * 输出：10<p>
 * 解释：最优子序列为 [6,1,5] ，交替和为 (6 + 5) - 1 = 10 。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 1 <= nums[i] <= 10^5<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximum-alternating-subsequence-sum">1911. 最大子序列交替和</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1911 {

    @Test
    public void test01() {
//        int[] nums = {4, 2, 5, 3};
//        int[] nums = {5, 6, 7, 8};
        int[] nums = {6, 2, 1, 2, 4, 5};
        System.out.println(new Solution().maxAlternatingSum(nums));
    }
}

class Solution {
    public long maxAlternatingSum(int[] nums) {
        // 交替和：偶数元素之和减去奇数下标之和
        // 获取子序列的最大交替和(子序列：原数组删除部分元素后组成)
        int n = nums.length;
        long ans = nums[n - 1];
        // 思考：如何保证偶数之和减去奇数之和最大？
        for (int i = 0; i < n - 1; i++) {
            // 高减低
            ans += Math.max(0, nums[i] - nums[i + 1]);
        }
        return ans;
    }
}
